package application;

import java.util.Arrays;
import java.util.LinkedList;

public class NQueens {
    private int n;
    private int[] records;
    private LinkedList<Character[][]> result;
    public NQueens() { }
    public void setN(int n) {
        this.n = n;
        this.records = new int[n];
        this.result = new LinkedList<>();
        Arrays.fill(this.records, -1);
    }
    private boolean isValid(int row, int col) {
        for (int i = 0; i < this.n; ++i) {
            // 第 col 列已有皇后
            if (this.records[i] == col) {
                return false;
            }
            // 斜对角线已有皇后
            if ( (row-i) == Math.abs(col-this.records[i]) ) {
                return false;
            }
        }
        return true;
    }
    private Character[][] generateBoard() {
        Character[][] board = new Character[this.n][this.n];
        for (int i = 0; i < this.n; ++i) {
            Character[] line = new Character[this.n];
            Arrays.fill(line, '*');
            line[this.records[i]] = 'Q';
            board[i] = line;
        }
        return board;
    }
    private void backtrace(int row) {
        if (row == this.n) {
            this.result.addLast( this.generateBoard() );
            return;
        }
        for (int col = 0; col < this.n; ++col) {
            if ( !this.isValid(row, col) ) {
                continue;
            }
            int temp = this.records[row];
            this.records[row] = col;
            this.backtrace(row+1);
            this.records[row] = temp;
        }
    }
    public LinkedList<Character[][]> solve() {
        this.backtrace(0);
        return this.result;
    }
    public static void printBoard(Character[][] board) {
        int n = board.length;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                sb.append(board[i][j]).append("  ");
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }
}
